package sorting;

import util.ArrayUtil;
import util.Tracer;

public class BooleanSort {
	public static int sort(Person[] persons, int p, int r)
	{
		if(p == r) return persons[p].isMale() ? 0 : 1;

		int femaleNum = 0;
		for(int i = p; i <= r; i ++)
		{
			if(!persons[i].isMale())
				femaleNum ++;
		}
		
		if(femaleNum != 0 && femaleNum != r - p + 1)
			sort(persons, p, r, femaleNum);
		return femaleNum;
	}
	
	private static void sort(Person[] persons, int p, int r, int femaleNum)
	{
		int q = p + femaleNum;
		int subFemaleNum1 = sort(persons, p, q - 1);
		
		if(subFemaleNum1 != femaleNum)
		{
			int subFemaleNum2 = femaleNum - subFemaleNum1;

			sort(persons, q, r, subFemaleNum2);
	
			int wrappedNum = 0;
			while(wrappedNum != subFemaleNum2)
			{
				ArrayUtil.each(persons, q + subFemaleNum2 - wrappedNum - 1, q - wrappedNum - 1);
				
				wrappedNum ++;
			}
		}
	}
	
	public static void main(String[] args) {
		Person[] persons = new Person[]{
				new Person(1, true),
				new Person(2, true),
				new Person(3, true),
				new Person(4, true),
				new Person(5, true),
				new Person(6, true),
				new Person(7, true),
				new Person(8, true),
		};
		sort(persons, 0, persons.length - 1);
		Tracer.trace(persons);
	}
}

class Person
{
	public Person(int num, boolean male) {
		setNum(num);
		setMale(male);
	}
	private int num;
	private boolean male;
	public int getNum() {
		return num;
	}
	public void setNum(int num) {
		this.num = num;
	}
	public boolean isMale() {
		return male;
	}
	public void setMale(boolean male) {
		this.male = male;
	}
	
	@Override
	public String toString() {
		return "(" + num + "," + male + ")";
	}
}
